//
//  main.c
//  03-快速排序(递归法)
//
//  Created by zhongad on 2017/1/10.
//  Copyright © 2017年 zhongad. All rights reserved.
//

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include "Swap.h"

void quick_sort_recursive(int arr[], int start, int end) {
    if (start >= end)
        return; // 這是為了防止宣告堆疊陣列時當機
    int mid = arr[end];
    int left = start, right = end - 1;
    while (left < right) {
        while (arr[left] < mid && left < right)
            left++;
        while (arr[right] >= mid && left < right)
            right--;
        swap(&arr[left], &arr[right]);
    }
    if (arr[left] >= arr[end])
        swap(&arr[left], &arr[end]);
    else
        left++;
    if (left) {
        quick_sort_recursive(arr, start, left - 1);
    }
    quick_sort_recursive(arr, left + 1, end);
}

void quick_sort(int arr[], int len) {
    quick_sort_recursive(arr, 0, len - 1);
}

// 所用时间:0.001259
int main(int argc, const char * argv[]) {
    // 计算时间
    int arr[10000];
    for (int i = 0; i < 10000; i++) {
        arr[i] = random() % 1000000;
    }
    int len = (int) sizeof(arr) / sizeof(*arr);
    clock_t start, end;
    start = clock();
    quick_sort(arr, len);
    end = clock();
    printf("所用时间:%f\n", (double)(end - start) / CLOCKS_PER_SEC);
    for (int i = 0; i < len; i++)
        printf("%d ", arr[i]);
    return 0;
}
